package Simple2;

import java.util.Iterator;
import java.util.LinkedList;

public class SearchRange {

	public static LinkedList<Integer> solution(int A[], int n, int target){
		int low=0;
		int high=n-1;
		int mid;
		int positionRecordLow=-1;
		int positionRecordHigh=-1;
		LinkedList<Integer> positionRecord = new LinkedList<Integer>();
		while(low<=high){
			mid=(low+high)/2;
			if(A[mid]<target)
				low=mid+1;
			else if (A[mid]>target)
					high=mid-1;
			else{
//				high=mid-1;
//				if(A[low]<target)
//					positionRecordLow = mid;
//				else {
//					positionRecordLow = low;
//				}
				
				positionRecordLow = mid;
//				if(A[--mid]==target){
//					high = mid;
//				}
//				else
					high=mid-1;
			}
				
		}
		
		if(positionRecordLow==-1){
			positionRecord.add(-1);
			positionRecord.add(-1);
			return positionRecord;
		}
		
		positionRecordHigh = positionRecordLow;
		low=positionRecordLow + 1;
		high=n-1;
		while(low<=high){
			mid=(low+high)/2;
			if(A[mid]<target)
				low=mid+1;
			else if(A[mid]>target)
					high=mid-1;
			else{
				positionRecordHigh = mid;
//				if(A[++mid]==target){
//					low = mid;
//				}
//				else
					low=mid+1;
//				low = mid +1;
//				if(A[high]>target)
//					positionRecordHigh = mid;
//				else {
//					positionRecordHigh = high;
//				}
			}
		}
		
		positionRecord.add(positionRecordLow);
		positionRecord.add(positionRecordHigh);
		return positionRecord;
		
	}
	
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		int[] A = {5,7,7,8,8,8,8,8,9};
		LinkedList<Integer> test = solution(A, A.length, 8);
		Iterator<Integer> flag = test.iterator();
		while(flag.hasNext()){
			System.out.print(flag.next().toString()+" ");
			
		}
		
		
	}

}
